package com.yinxin.wudasuanfa.huaweiod;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，
 * 推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。
 * @date 2022/5/1221:11
 */
public class Exercise11Hard {
   public static void main(String[] args) {
      int[][] arr = {{0,9,2,4,8,1,7,6,3},{4,1,3,7,6,2,9,8,5},{8,6,7,3,5,9,4,1,2},
              {6,2,4,1,9,5,3,7,8},{7,5,9,8,4,3,1,2,6},{1,3,8,6,2,7,5,9,4},
              {2,7,1,5,3,8,6,4,9},{3,8,6,9,1,4,2,5,7},{0,4,5,2,7,6,8,3,1}};
      /*for (int i = 0; i < 9; i++) {
         for (int j = 0; j < 9; j++) {
            int anInt = sc.nextInt();
            if(anInt>=0&&anInt<=9){
               arr[i][j]=anInt;
            }else {
               j--;
            }
         }
      }*/

      solveSudoku(arr);
      for (int i = 0; i < arr.length; i++) {
         for (int j = 0; j < arr[i].length; j++) {
            System.out.print(arr[i][j]+" ");
         }
         System.out.println();
      }

   }
   public static boolean solveSudoku(int[][] board){
      //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
      // 一行一***定下来之后，递归遍历这个位置放9个数字的可能性！」
      for (int i = 0; i < 9; i++){ // 遍历行
         for (int j = 0; j < 9; j++){ // 遍历列
            if (board[i][j] != 0){ // 跳过原始数字
               continue;
            }
            for (int k = 1; k <= 9; k++){ // (i, j) 这个位置放k是否合适
               if (check(board,i, j, k)){
                  board[i][j] = k;//将k放在（i，j）
                  if (solveSudoku(board)){ // 如果找到合适一组立刻返回
                     return true;
                  }
                  board[i][j] = 0;//回溯
               }
            }
            // 9个数都试完了，都不行，那么就返回false
            return false;
            // 因为如果一行一***定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
            // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
         }
      }
      // 遍历完没有返回false，说明找到了合适棋盘位置了
      return true;
   }
   public static boolean check(int[][] arr,int row,int col,int val){
      //同行
      for(int i = 0; i < 9; i++) {
         if(arr[row][i] == val) {
            return false;
         }
      }
      //同列
      for(int i = 0; i < 9; i++) {
         if(arr[i][col] == val) {
            return false;
         }
      }
      //同一个九宫格
      int limit_row = row / 3 * 3 + 3;//九宫格行的终点
      int limit_col = col / 3 * 3 + 3;//九宫格列的终点
      for(int i = limit_row - 3; i < limit_row; i++) {
         for(int j = limit_col - 3; j < limit_col; j++) {
            if(arr[i][j] == val) {
               return false;
            }
         }
      }
      return true;
   }
}
